'''
https://leetcode.cn/problems/reorder-list/description/
'''
from typing import Optional


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        return str(self.val)


class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        cur = head
        help = []
        while cur:
            help.append(cur)
            cur = cur.next

        l, r = 0, len(help) - 1
        while l < r:
            help[r].next = help[l].next
            help[l].next = help[r]
            l += 1
            r -= 1
        help[l].next = None

    def reorderList2(self, head: Optional[ListNode]) -> None:
        def reverse(head):
            prev = None
            while head:
                next = head.next
                head.next = prev
                prev = head
                head = next
            return prev

        def mid(head):
            slow, fast = head, head
            while fast.next and fast.next.next:
                slow = slow.next
                fast = fast.next.next
            return slow

        m = mid(head)
        last_part = reverse(m.next)
        a, b = head, last_part
        while b:
            next1, next2 = a.next, b.next
            a.next = b
            b.next = next1
            a, b = next1, next2
        a.next = None


def list_print(head):
    cur = head
    while cur:
        print(cur.val, end=" -> ")
        cur = cur.next
    print()


head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
list_print(head)
Solution().reorderList2(head)
list_print(head)
